542. 01 矩阵

Similar Question

Solution Tips

方案一: 错误的尝试 Dfs

var updateMatrix = function(grid) {
    // 和网格问题的岛屿问题很像, 遍历方式很像, 找到 1 然后分叉遍历
    // 同时也有最短路径算法的身影, 记录前溯点的值, 然后 + 1即可, 这个做法本身是分治思想
    // 这题不能填充, 因为四周没有默认是海... 所以填充0的会影响判断, 只能填充无穷大, 但是也不能填充无穷大
    // 因为数据会溢出...
    // inArea 虽然会浪费一点时间复杂度, 但其实才是最简单的处理
    // 每次递归前判断是否越界, 就没有办法想这次放进数组里求最小值了...
    // const startRow = Array.from({length: grid[0].length}, () => Number.MAX_SAFE_INTEGER1);
    // const endRow = Array.from({length: grid[0].length}, () => Number.MAX_SAFE_INTEGER);
    // grid.unshift(startRow);
    // grid.push(endRow);
    // 为什么最短路径的题目, 我要使用 dfs 呢? ...
    let visited = {};

    for (let i = 1; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === 1) {
                dfs(i, j);
                visited[`${i}${j}`] = true;
            }
        }
    }

    return grid;


    function dfs(r, c) {
        if (!inArea(grid, r, c)) return Number.MAX_SAFE_INTEGER;
        if (visited[[r,c].join('')] || grid[r][c] === 0) return grid[r][c] + 1;

        // 已经遍历过的岛屿标记为 2, 这一次遍历过也 ok? 这次不太好在元素组标记了
        // 最好是另外建一个数组标记, 但是好像不标记影响也不大
        // grid[r][c] = '2';

        // 每一个点都需要重新出发做遍历

        // 继续递归四个方向
        const aroundDistance = [
            dfs(r - 1, c),
            dfs(r + 1, c),
            dfs(r, c + 1),
            dfs(r, c - 1),
        ]

        // 返回四个方向中的最短路径
        return grid[r][c] = aroundDistance.reduce((min, a) => Math.min(min, a));
    }

    function inArea(grid, r, c) {
        // 仔细想一下这个判断其实很重复, 有点没有必要
        // 首先 r 只有第一行和最后一行可能越界
        // 然后 col 即使越界了也没有关系, 读取到 undefined, bad case 直接结束递归了
        // 所以只需要给最开头和最后加上一个填充行就好了
        if (r > grid.length - 1 || c > grid[0].length - 1) return false;
        if (r < 0 || c < 0) return false;
        return true;
    }

};